#pragma once
#include <stdio.h>

typedef struct NodeData 
{
	int mValue;
	int compare(NodeData* p) {
		if (p) {
			return mValue > p->mValue ? 1 : mValue == p->mValue ? 0 : -1;
		}
		return -2;
	}

} *pNodeData;

enum NODE_COLOR { RED, BLACK };
typedef struct TreeNode
{
	TreeNode *parent;
	TreeNode *left;
	TreeNode *right;
	int color;
	pNodeData m_pData;
} *pTreeNode;


class RedBlackTree
{
	pTreeNode mRoot;
	const pTreeNode nil;

	void left_rotate(pTreeNode pivot);
	void right_rotate(pTreeNode pivot);

	bool _insert(pTreeNode root, pTreeNode node);
	void insert_adjust(pTreeNode node);	
	void _delete(pTreeNode node);
	
	bool is_not_leaf(pTreeNode node);
	pTreeNode grandparent(pTreeNode node);
	pTreeNode uncle(pTreeNode node);
	pTreeNode sibling(pTreeNode node);

	pTreeNode createNode(pNodeData data);

public:
	RedBlackTree(void);
	~RedBlackTree(void);

	void insert(pNodeData node);
	void deleteData(pNodeData pData);
	pTreeNode search(pNodeData pData);

	bool check_tree();
};
